﻿#pragma once
#include "Index.h"

class IMaxStudentsTakeExam
{
public:
	virtual int maxStudents(std::vector<std::vector<char>>& seats) = 0;
};

class MaxStudentsTakeExam
{
public:
	class DP :public IMaxStudentsTakeExam
	{
	public:
		int maxStudents(std::vector<std::vector<char>>& seats) override
		{
			if (seats.empty() || seats.front().empty())
				return 0;

			_seats = &seats;
			_row = seats.size();
			_col = seats.front().size();

			//可用座位被坐和不坐的情况
			long long state = 0;
			return maxStudents(-1, -1, state);
		}
	public:
		//计算在给定的(seatx,seaty)位置后面可容纳的最大学生数
		int maxStudents(int seatx, int seaty, long long& state)
		{
			int seatBit = nextSeatBit(seatx, seaty);
			//后面没有可用座位
			if (seatBit < 0)
				return 0;

			seatx = seatBit / _col;
			seaty = seatBit % _col;

			//不坐的情况
			long long prestate = state;
			int skipSeat = maxStudents(seatx, seaty, state);
			EXPECT_EQ(prestate, state);

			//坐的情况
			int takeSeat = 0;
			if (canTakeSeat(seatx, seaty, state))
			{
				long long seatFlag = seatx * _col + seaty;
				seatFlag = 1LL << seatFlag;

				prestate = state;
				state |= seatFlag;
				takeSeat = 1 + maxStudents(seatx, seaty, state);
				state &= ~seatFlag;
				EXPECT_EQ(prestate, state);
			}
			return std::max<int>(skipSeat, takeSeat);
		}

		//找到下一个可用座位,返回座位从二维位置转换为一维的位置
		int nextSeatBit(int seatx, int seaty)
		{
			if (seatx < 0 || seaty < 0)//找到第一个可用座位
			{
				for (int i = 0; i < _row; ++i)
					for (int j = 0; j < _col; ++j)
					{
						if ((*_seats)[i][j] == '.')
							return (i *_col  + j);
					}
			}
			else //(seatx,seaty)后面的下一个可用座位
			{
				//同行后面的列
				if(seatx>=0 && seatx<_row)
				{
					for (int j = seaty + 1; j < _col; ++j)
					{
						if ((*_seats)[seatx][j] == '.')
							return (seatx * _col + j);
					}
				}

				//矩阵中后面的行
				for (int i = seatx + 1; i < _row; ++i)
					for (int j = 0; j < _col; ++j)
					{
						if ((*_seats)[i][j] == '.')
							return (i * _col + j);
					}
			}

			return -1;//返回负数表示没有可用座位
		}

		//给定的座位是否可坐下?提供的(seatx,seaty)保证是空的可用座位
		bool canTakeSeat(int seatx, int seaty, long long& state)
		{
			static std::vector<std::vector<int>> neighbours
				= { {0,-1},{0,+1},{-1,-1},{-1,+1} };//左,右,左上,右上

			for (auto& neighbour : neighbours)
			{
				int neigh_x = seatx + neighbour[0];
				int neigh_y = seaty + neighbour[1];

				//越界
				if (neigh_x < 0 || neigh_x >= _row
					|| neigh_y < 0 || neigh_y >= _col)
					continue;

				//有学生做过,可以被作弊
				long long seatFlag = neigh_x * _col + neigh_y;
				seatFlag = 1LL << seatFlag;
				if (state & seatFlag)
					return false;
			}
			return true;
		}

		std::vector<std::vector<char>>* _seats;
		int _row, _col;
	};
};

#ifdef DEV_TEST
#include "gtest/gtest.h"

TEST(MaxStudentsTakeExam, maxStudents)
{
	TEST_SOLUTION1(IMaxStudentsTakeExam, MaxStudentsTakeExam::DP, &)
	{
		std::vector<std::vector<char>> seats = {{'.','#','.'},{'#','.','.'}};// { {'.', '#'}, { '#','#' }, { '#','.' }, { '#','#' }, { '.','#' }};
		EXPECT_EQ(3, solution->maxStudents(seats));
	};
}

TEST(MaxStudentsTakeExam, maxStudents2)
{
	TEST_SOLUTION1(IMaxStudentsTakeExam, MaxStudentsTakeExam::DP, &)
	{
		std::vector<std::vector<char>> seats = 
			{{'#','.','.','.','#'},
			{'.','#','.','#','.'},
			{'.','.','#','.','.'},
			{'.','#','.','#','.'},
			{'#','.','.','.','#'}};
		EXPECT_EQ(10, solution->maxStudents(seats));
	};
}

TEST(MaxStudentsTakeExam, nextSeatBit)
{
	TEST_SOLUTION1(IMaxStudentsTakeExam, MaxStudentsTakeExam::DP, &)
	{
		MaxStudentsTakeExam::DP* s = dynamic_cast<MaxStudentsTakeExam::DP*>(solution);

		std::vector<std::vector<char>> seats =
		{ {'#','.','.','.','#'},
		{'.','#','.','#','.'},
		{'.','.','#','.','.'},
		{'.','#','.','#','.'},
		{'#','.','.','.','#'} };

		int row = seats.size();
		int col = seats.front().size();
		s->_row = row;
		s->_col = col;
		s->_seats = &seats;

		int seatBit= s->nextSeatBit(-1, -1);
		for(int i=0;i<row;++i)
			for(int j=0;j<col;++j)
			{
				if(seats[i][j]=='.')
				{
					int curSeat= i* row + j;
					EXPECT_EQ(curSeat, seatBit);
					seatBit= s->nextSeatBit(i,j);
				}
			}

		EXPECT_EQ(seatBit, -1);
	};
}
#endif